package chapter2;

import util.PrintUtils;

public class QuickSort {

    public void sort(int[] orig) {
        if (orig == null || orig.length == 1) return;

        work(orig, 0, orig.length - 1);
    }

    private void work(int[] og, int p, int q) {
        if (p < q) {
            int p1 = p, q1 = q;
            int z = og[p];
            while (p1 < q1) {
                while (p1 < q1 && og[q1] > z) {
                    q1 --;
                }
                og[p1] = og[q1];
                while (p1 < q1 && og[p1] <= z) {
                    p1 ++;
                }
                og[q1] = og[p1];
            }
            og[p1] = z;
            work (og, p, p1);
            work(og, p1+1, q);
        }
    }


    public static void main(String[] args) {
        int a[] = {30,40,60,10,20,50, 1};
        new  QuickSort().sort(a);
        PrintUtils.PrintArray(a);
    }
}
